public class AVLTree {
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        tree.insert(10);
        tree.insert(50);
        tree.insert(40);
        tree.insert(30);
        tree.insert(20);
        System.out.println();
    }

    static class TreeNode{
        private int val ;
        private TreeNode left ;
        private TreeNode right ;
        private TreeNode parent ;
        private int bf ;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    private TreeNode root ;

    public void insert(int val){
        TreeNode node = new TreeNode(val);
        if(this.root == null){
            this.root = node;
            return;
        }

        TreeNode cur = root;
        TreeNode parent = null ;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else{
                parent = cur ;
                cur = cur.left ;
            }

        }
        if (parent.val > val) {
            parent.left = node ;
            node.parent = parent ;
        }else{
            parent.right = node ;
            node.parent = parent ;
        }
        cur = node ;
        while (parent != null) {
            if (cur == parent.left) {
                parent.bf -- ;
            }else{
                parent.bf ++ ;
            }

            if (parent.bf == 0) {
                break;
            } else if (parent.bf == 1 || parent.bf == -1) {
                cur = parent ;
                parent = cur .parent;
            }else{
                if (parent.bf == 2) {
                    if(cur.bf == 1){
                        // 左旋
                        rotateLeft(parent);
                    }else{
                        // 右左双旋
                        rotateRL(parent);
                    }
                }else{
                    if(cur.bf == 1){
                        // 左右双旋
                        rotateLR(parent);
                    }else{
                        //右旋
                        rotateRight(parent);
                    }
                }
                // 进行旋转之后,树已经平衡了
                break;
            }
        }


    }

    private void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left ;
        TreeNode subLR = subL.right ;
        int bf = subLR.bf ;
        rotateLeft(subL);
        rotateRight(parent);
        if(bf == 1){
            subL.bf = -1;
            parent.bf = 0 ;
            subLR.bf = 0 ;
        }else{
            subL.bf = 0 ;
            subLR.bf = 0 ;
            parent.bf = 1 ;
        }
    }

    private void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right ;
        TreeNode subRL = subR.left;
         int bf = subRL.bf ;
         // 右旋
        rotateRight(subR);
        rotateLeft(parent);
        if(bf == 1){
         subRL.bf = 0;
         parent.bf = -1 ;
         subR .bf = 0 ;
        }else{
            parent.bf = 0 ;
            subRL.bf = 0 ;
             subR.bf = 1 ;
        }
    }

    private void  rotateRight(TreeNode parent) {
        TreeNode subL  = parent.left ;
        TreeNode subLR = subL.right ;
        parent.left = subLR ;
        if (subLR != null) {
            subLR.parent = parent ;
        }
        if (this.root == parent) {
            this.root = subL;
            root.parent = null ;
        }else{
            TreeNode pParent = parent.parent ;
            if(parent == pParent.left){
                pParent.left = subL;
                subL.parent = pParent ;
            }else{
                pParent.right = subL;
                subL.parent = pParent;
            }
            subL.right = parent ;
            parent.parent = subL;
            subL.bf = 0 ;
            parent.bf = 0 ;
        }

    }

    // 左旋
    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right ;
        TreeNode subRL = subR.left ;
        parent.right = subRL ;
        if (subRL != null) {
            subRL.parent = parent ;
        }
        if (parent == this.root) {
            this.root = subR ;
            this.root.parent = null ;
        }else{
            TreeNode pParent = parent.parent ;
            if(parent == pParent.left){
                subR.parent = pParent ;
                pParent.left = subR ;
            }else{
                subR.parent = pParent;
                pParent.right = subR;
            }

        }
        subR.left = parent;
        parent.parent = subR ;
        parent.bf = 0 ;
        subR.bf = 0 ;
    }




}
